{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Prefix Common Array of Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findThePrefixCommonArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到两个数组的前缀公共数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数排列&nbsp;<code>A</code> 和&nbsp;<code>B</code>&nbsp;。</p>\n",
    "\n",
    "<p><code>A</code>&nbsp;和&nbsp;<code>B</code>&nbsp;的 <strong>前缀公共数组</strong>&nbsp;定义为数组&nbsp;<code>C</code>&nbsp;，其中&nbsp;<code>C[i]</code>&nbsp;是数组&nbsp;<code>A</code> 和&nbsp;<code>B</code>&nbsp;到下标为&nbsp;<code>i</code>&nbsp;之前公共元素的数目。</p>\n",
    "\n",
    "<p>请你返回 <code>A</code>&nbsp;和 <code>B</code>&nbsp;的 <strong>前缀公共数组</strong>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个长度为 <code>n</code>&nbsp;的数组包含 <code>1</code>&nbsp;到 <code>n</code>&nbsp;的元素恰好一次，我们称这个数组是一个长度为 <code>n</code>&nbsp;的 <strong>排列</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>A = [1,3,2,4], B = [3,1,2,4]\n",
    "<b>输出：</b>[0,2,3,4]\n",
    "<b>解释：</b>i = 0：没有公共元素，所以 C[0] = 0 。\n",
    "i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。\n",
    "i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。\n",
    "i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>A = [2,3,1], B = [3,1,2]\n",
    "<b>输出：</b>[0,1,3]\n",
    "<b>解释：</b>i = 0：没有公共元素，所以 C[0] = 0 。\n",
    "i = 1：只有 3 是公共元素，所以 C[1] = 1 。\n",
    "i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= A.length == B.length == n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= A[i], B[i] &lt;= n</code></li>\n",
    "\t<li>题目保证&nbsp;<code>A</code>&nbsp;和&nbsp;<code>B</code>&nbsp;两个数组都是&nbsp;<code>n</code>&nbsp;个元素的排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-prefix-common-array-of-two-arrays](https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-prefix-common-array-of-two-arrays](https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,4]\\n[3,1,2,4]', '[2,3,1]\\n[3,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        count = len(A)\n",
    "        for i in range(count):\n",
    "            result.append(len(set(A[:i+1]) & set(B[:i+1])))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        dictA = {}\n",
    "        dictB = {}\n",
    "        n = len(A)\n",
    "        cnt = 0\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            if A[i]==B[i]:\n",
    "                cnt = cnt+1\n",
    "            else:\n",
    "                if A[i] in dictB:\n",
    "                    cnt = cnt+1\n",
    "                else:\n",
    "                    dictA[A[i]] = 1\n",
    "                \n",
    "                if B[i] in dictA:\n",
    "                    cnt = cnt+1\n",
    "                else:\n",
    "                    dictB[B[i]] = 1\n",
    "            l.append(cnt)\n",
    "        \n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        sa, sb = set(), set()\n",
    "        ans = []\n",
    "        for a, b in zip(A, B):\n",
    "            sa.add(a)\n",
    "            sb.add(b)\n",
    "            ans.append(len(sa & sb))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        s = set()\n",
    "        t = set()\n",
    "        for x, y in zip(A, B):\n",
    "            s.add(x)\n",
    "            t.add(y)\n",
    "            ans.append(len(s&t))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        a = []\n",
    "        b = []\n",
    "        ans = []\n",
    "        for i in range(len(A)):\n",
    "            a.append(A[i])\n",
    "            b.append(B[i])\n",
    "            ans.append(len(set(a) & set(b)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        return [len(set(A[:i]) & set(B[:i])) for i in range(1, len(A) + 1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)\n",
    "        ans = [] \n",
    "        setA , setB = set(),set() \n",
    "        for i in range(n) :\n",
    "            setA.add(A[i]) \n",
    "            setB.add(B[i])\n",
    "            # 求交集的元素数\n",
    "            ans.append(len(setA.intersection(setB)))\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        sta = set()\n",
    "        stb = set()\n",
    "        n = len(A)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            sta.add(A[i])\n",
    "            stb.add(B[i])\n",
    "            ans[i] = len(sta & stb)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)\n",
    "        res = [0] * n\n",
    "        if A[0] == B[0]:\n",
    "            res[0] = 1\n",
    "        for i in range(1, n):\n",
    "            res[i] += res[i-1]\n",
    "            if A[i] in B[:i+1]:\n",
    "                res[i] += 1\n",
    "            if B[i] in A[:i+1] and B[i] != A[i]:\n",
    "                res[i] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0 \n",
    "        for x , y in zip(A,B) :\n",
    "            p |= 1 << x \n",
    "            q |= 1 << y \n",
    "            ans.append((p&q).bit_count())\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        s1 = set()\n",
    "        s2 = set()\n",
    "        ans = []\n",
    "        for i in range(len(A)):\n",
    "            s1.add(A[i])\n",
    "            s2.add(B[i])\n",
    "            ans.append(len(s1.intersection(s2)))\n",
    "            # ans[i] = len(s1.intersection(s2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        p =q = 0\n",
    "        for x,y in zip(A,B):\n",
    "            p|= 1<<x\n",
    "            q |= 1<<y\n",
    "            ans.append((p&q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        a = b = 0\n",
    "        for x, y in zip(A, B):\n",
    "            a |= 1 << x\n",
    "            b |= 1 << y\n",
    "            ans.append((a & b).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        cnt=Counter()\n",
    "        n=len(A)\n",
    "        ans=[0]*n\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            ai,bi=A[i],B[i]\n",
    "            cnt[ai]+=1\n",
    "            if cnt[ai]==0:\n",
    "                cur+=1\n",
    "            cnt[bi]-=1\n",
    "            if cnt[bi]==0:\n",
    "                cur+=1\n",
    "            ans[i]=cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        p=q=0\n",
    "        for x,y in zip(A,B):\n",
    "            p|=1<<x\n",
    "            q|=1<<y\n",
    "            ans.append((p&q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)\n",
    "        set_a = set()\n",
    "        set_b = set()\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            set_a.add(A[i])\n",
    "            set_b.add(B[i])\n",
    "            res.append(len(set_a&set_b))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        length = len(A)\n",
    "        ta = 0\n",
    "        ts = set()\n",
    "        for i in range(length):\n",
    "            if A[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(A[i])\n",
    "            else:\n",
    "                ts.add(A[i])\n",
    "            if B[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(B[i])\n",
    "            else:\n",
    "                ts.add(B[i])\n",
    "            ans.append(ta)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        count = len(A)\n",
    "        \n",
    "        # result = []\n",
    "        # for i in range(count):\n",
    "        #     result.append(len(set(A[:i+1]) & set(B[:i+1])))\n",
    "        return [len(set(A[:i+1]) & set(B[:i+1])) for i in range(count)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        vis = [1] * (len(A) + 1)\n",
    "        x = 0\n",
    "        for a, b in zip(A, B):\n",
    "            vis[a] ^= 1\n",
    "            x += vis[a]\n",
    "            vis[b] ^= 1\n",
    "            x += vis[b]\n",
    "            ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 利用位运算加速\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n=len(A)\n",
    "        sset=set()\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            sset.add(A[i])\n",
    "            cnt=0\n",
    "            for j in range(i+1):\n",
    "                if B[j] in sset:\n",
    "                    cnt+=1\n",
    "            arr.append(cnt)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        X = []\n",
    "        for i in range(0,len(A)):\n",
    "            sum = 0\n",
    "            for j in range(0,i+1):\n",
    "                if A[j] in B[:i+1]:\n",
    "                    sum += 1\n",
    "            X.append(sum)\n",
    "        return X\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(A)):\n",
    "            a, b = set(A[:i+1]), set(B[:i+1])\n",
    "            res.append(i+1-len(a-b))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        vis = [1] * (len(A) + 1)\n",
    "        s = 0\n",
    "        for a, b in zip(A, B):\n",
    "            vis[a] ^= 1\n",
    "            s += vis[a]\n",
    "            vis[b] ^= 1\n",
    "            s += vis[b]\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(A)\n",
    "        vis = [1] * (n + 1)\n",
    "        x = 0\n",
    "        for a, b in zip(A, B):\n",
    "            vis[a] ^= 1\n",
    "            x += vis[a]\n",
    "            vis[b] ^= 1\n",
    "            x += vis[b]\n",
    "            ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        start = 0\n",
    "        result = [0]\n",
    "        while start < len(A):\n",
    "            result.append(result[-1])\n",
    "            if A[start] == B[start]:\n",
    "                result[-1] += 1\n",
    "            else:\n",
    "                if A[start] in B[:start]:\n",
    "                    result[-1] += 1\n",
    "                if B[start] in A[:start]:\n",
    "                    result[-1] += 1\n",
    "            start += 1\n",
    "        return result[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        arr1 = 0\n",
    "        arr2 = 0\n",
    "        n = len(A)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            arr1 ^= (1 << A[i])\n",
    "            arr2 ^= (1 << B[i])\n",
    "            v = arr1 & arr2\n",
    "            ans.append(v.bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        num_dic = collections.defaultdict(int)\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        for i in range(len(A)):\n",
    "            num_dic[A[i]] += 1\n",
    "            if num_dic[A[i]] == 2:\n",
    "                cnt += 1\n",
    "            num_dic[B[i]] += 1\n",
    "            if num_dic[B[i]] == 2:\n",
    "                cnt += 1\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        #copy\n",
    "        ans = []\n",
    "        p=q=0\n",
    "        for x,y in zip(A,B):\n",
    "            p |=1<<x\n",
    "            q|=1<<y\n",
    "            ans.append((p&q).bit_count())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        wa\n",
    "        ans = []\n",
    "        res = []\n",
    "        for i in range(len(A)):\n",
    "            if A[i] in B and B[i] not in A:\n",
    "                ans.append(1) \n",
    "            elif B[i] in A and B[i] not in A:\n",
    "                res.append(1)\n",
    "            elif B[i] in A and  A[i] in B:\n",
    "                ans.append(1)\n",
    "                res.append(0)\n",
    "\n",
    "\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        \n",
    "        \n",
    "        ret = [0]\n",
    "        cnt  =0\n",
    "        for i in range(1,len(A)):\n",
    "            cnt += ans[i-1]+res[i-1]\n",
    "            ret.append(cnt)\n",
    "        return ret'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        def findCommon(A,B):\n",
    "            A.sort()\n",
    "            B.sort()\n",
    "            n = len(A)\n",
    "            count = 0\n",
    "            point_A, point_B= 0, 0\n",
    "            while point_A < n and point_B < n:\n",
    "                if A[point_A] == B[point_B]:\n",
    "                    count += 1\n",
    "                    point_A += 1\n",
    "                    point_B += 1\n",
    "                elif A[point_A] < B[point_B]:\n",
    "                    point_A += 1\n",
    "                else:\n",
    "                    point_B += 1\n",
    "            \n",
    "            return count\n",
    "        n = len(A)\n",
    "        C = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            C[i] = findCommon(A[:i + 1],B[:i + 1])\n",
    "        return C\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n=len(A)\n",
    "        p=[]\n",
    "        if A[0]==B[0]:\n",
    "            ans=[1]\n",
    "        else:\n",
    "            ans=[0]\n",
    "        for i in range(1,n):\n",
    "            t=0\n",
    "            if A[i] not in p:\n",
    "                if A[i] in B[:i]:\n",
    "                    t+=1\n",
    "                if A[i]==B[i]:\n",
    "                    ans.append(1+ans[-1])\n",
    "                    continue\n",
    "            if B[i] not in p:\n",
    "                if B[i] in A[:i]:\n",
    "                    t+=1\n",
    "            ans.append(t+ans[-1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)  \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(len(set(A[:i+1]) & set(B[:i+1])))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)\n",
    "        ans = [0] * n\n",
    "        if A[0] == B[0]:\n",
    "            ans[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if A[i] == B[i]:\n",
    "                ans[i] = ans[i - 1] + 1\n",
    "            else:\n",
    "                num = 0\n",
    "                if A[i] in B[:i]:\n",
    "                    num += 1\n",
    "                if B[i] in A[:i]:\n",
    "                    num += 1\n",
    "                ans[i] = ans[i - 1] + num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        aCount = {}\n",
    "        bCount = {}\n",
    "        LEN = len(A)\n",
    "        for i in range(LEN):\n",
    "            add = 0\n",
    "            if A[i]==B[i]:\n",
    "                add += 1\n",
    "            else:\n",
    "                if aCount.get(A[i],0)<bCount.get(A[i], 0):\n",
    "                    add+=1\n",
    "                if bCount.get(B[i], 0)<aCount.get(B[i], 0):\n",
    "                    add+=1\n",
    "            res.append(res[-1]+add if i>0 else add)\n",
    "\n",
    "            aCount[A[i]] = aCount.get(A[i], 0) + 1\n",
    "            bCount[B[i]] = bCount.get(B[i], 0) + 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n=len(A)\n",
    "        C=[0]*n\n",
    "        for i in range(n):\n",
    "            a=set(A[:i+1])\n",
    "            b=set(B[:i+1])\n",
    "            c=a&b\n",
    "           # print(a,b,c)\n",
    "            C[i]=len(c)\n",
    "        return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        # C = [n]\n",
    "        # n = len(A)\n",
    "        # for i in range(n):\n",
    "        #     C.append(0)\n",
    "        #     for j in range(i+1):\n",
    "        #         if A[j] in B[:i+1]:\n",
    "        #             C[i] += 1\n",
    "        # return C\n",
    "\n",
    "        # 重复元素，采用集合实现 set()\n",
    "        s = set()\n",
    "        C = [len(A)]\n",
    "        for i in range(len(A)-1, 0, -1):\n",
    "            s.add(A[i])\n",
    "            s.add(B[i])\n",
    "            C.append(len(A) - len(s))\n",
    "        return C[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(A, B):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n = len(A)\n",
    "        res = [0] * n\n",
    "        if A[0] == B[0]:\n",
    "            res[0] = 1\n",
    "        for i in range(1, n):\n",
    "            res[i] += res[i-1]\n",
    "            if A[i] in B[:i+1]:\n",
    "                res[i] += 1\n",
    "            if B[i] in A[:i+1] and B[i] != A[i]:\n",
    "                res[i] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for i in range(len(A)):\n",
    "            temp=0\n",
    "            for j in A[:i+1]:\n",
    "                if j in B[:i+1]:\n",
    "                    temp+=1\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "      n = len(A)\n",
    "      answer = [0] * n\n",
    "      set_a, set_b = set(), set()\n",
    "\n",
    "      for i in range(n):\n",
    "        set_a.add(A[i])\n",
    "        set_b.add(B[i])\n",
    "        answer[i] = len(set_a.intersection(set_b))\n",
    "\n",
    "      return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        C = []\n",
    "        # if A[0] == B[0] and A != [] and B != []:\n",
    "            # C.append(1)\n",
    "        for i in range(1, len(A) + 1):\n",
    "            C.append(0)\n",
    "            for j in A[:i]:\n",
    "                if j in B[:i]:\n",
    "                    C[i - 1] += 1\n",
    "        return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(a, b):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        length = len(A)\n",
    "        ta = 0\n",
    "        ts = set()\n",
    "        for i in range(length):\n",
    "            if A[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(A[i])\n",
    "            else:\n",
    "                ts.add(A[i])\n",
    "            if B[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(B[i])\n",
    "            else:\n",
    "                ts.add(B[i])\n",
    "            ans.append(ta)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(A)):\n",
    "            t_a = sorted(A[:i+1])\n",
    "            t_b = sorted(B[:i+1])\n",
    "            temp = set(t_a + t_b)\n",
    "            if len(temp) < 2 * len(t_a):\n",
    "                res.append(2*len(t_a) - len(temp))\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(A)):\n",
    "            res.append(len(set(A[0:i+1]) & set(B[0:i+1])))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        dic, res, pres = [0 for _ in range(len(A) + 1)], [], 0\n",
    "        for i in range(len(A)):\n",
    "            if dic[A[i]]:\n",
    "                pres += 1\n",
    "            else:\n",
    "                dic[A[i]] = 1\n",
    "            if dic[B[i]]:\n",
    "                pres += 1\n",
    "            else:\n",
    "                dic[B[i]] = 1\n",
    "            res.append(pres)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        n = len(A)\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            set1.add(A[i])\n",
    "            set2.add(B[i])\n",
    "            result.append(len(set1 & set2))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        a=set()\n",
    "        b=set()\n",
    "        c=[]\n",
    "        for i in range(len(A)):\n",
    "            a.add(A[i])\n",
    "            b.add(B[i])\n",
    "            c.append(len(a.intersection(b)))\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        length = len(A)\n",
    "        ta = 0\n",
    "        ts = set()\n",
    "        for i in range(length):\n",
    "            if A[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(A[i])\n",
    "            else:\n",
    "                ts.add(A[i])\n",
    "            if B[i] in ts:\n",
    "                ta+=1\n",
    "                ts.remove(B[i])\n",
    "            else:\n",
    "                ts.add(B[i])\n",
    "            ans.append(ta)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x, y in zip(A, B):\n",
    "            p |= 1 << x\n",
    "            q |= 1 << y\n",
    "            ans.append((p & q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        n=len(A)\n",
    "        for i in range(n):\n",
    "            res+=[len(set.intersection(set(A[:i+1]),set(B[:i+1])))]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        p = q = 0\n",
    "        for x,y in zip(A,B):\n",
    "            p |= (1<<x)\n",
    "            q |= (1<<y)\n",
    "            ans.append((p&q).bit_count())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        # 维护一个记录每个数字出现个数的数组\n",
    "        count = [0]*51\n",
    "        result = []\n",
    "        n = len(A)\n",
    "        for i in range(n):\n",
    "            count[A[i]]+=1\n",
    "            count[B[i]]+=1\n",
    "            result.append(count.count(2))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        n=len(A)\n",
    "        s1=set()\n",
    "        s2=set()\n",
    "        now=0\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            s1.add(A[i])\n",
    "            s2.add(B[i])\n",
    "            if A[i]==B[i]:\n",
    "                now+=1\n",
    "            else:\n",
    "                if A[i]in s2:\n",
    "                    now+=1\n",
    "                if B[i]in s1:\n",
    "                    now+=1\n",
    "            ans.append(now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(A)\n",
    "        f1 = [0] * n \n",
    "        f2 = [0] * n \n",
    "        f1[0] = (1 << A[0])\n",
    "        f2[0] = (1 << B[0])\n",
    "\n",
    "        def num_bits(x):\n",
    "            cnt = 0\n",
    "            for i in range(64):\n",
    "                if (x >> i) & 1:\n",
    "                    cnt += 1\n",
    "            return cnt \n",
    "        ans = []\n",
    "        ans.append(num_bits(f1[0] & f2[0]))\n",
    "        for i in range(1, n):\n",
    "            f1[i] = f1[i-1] | (1 << A[i])\n",
    "            f2[i] = f2[i-1] | (1 << B[i])\n",
    "            ans.append(num_bits(f1[i]&f2[i]))\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
